#include <stdio.h>
#include <stdlib.h> 
#include "linklist.h"

//创建
linklist list_create(){

    linklist H = ( linklist )malloc( sizeof( listnode ) );

    if( H == NULL )
    {
	printf("malloc failed\n");
	return H;
    }

    H->data = 0;
    H->next = NULL;

}

//尾部插入元素
int list_tail_insert( linklist H, data_t value ){

    if( H == NULL )
    {
	printf( "H is NULL\n" );
	return -1;
    }

    linklist p = ( linklist )malloc( sizeof( listnode) );
    linklist q;
    if( p == NULL )
    {
	printf("malloc failed\n");
	return -1;
    }

    p->data = value;
    p->next = NULL;

    q = H;
    while( q->next != NULL )
    {
	q = q->next;
    }

    q->next = p;

    return 1;
} 

//指定节点取值
linklist list_get( linklist H, int pos ){

    if( H == NULL )
    {
	printf( "H is NULL\n" );
	return NULL;
    }

    if( pos == -1 )
    {
	return H;
    }

    if( pos <-1 )
    {
	printf("pos is invalid\n");
	return NULL;
    }

    linklist p = H;
    while( pos > -1 )
    {

	if( p->next == NULL )
	{
	    printf( "pos is invalid\n" );
	    return NULL;
	}

	p = p->next;

	pos--;
    }

    return p;

}

//指定节点插入元素
int list_insert( linklist H, data_t value, int pos ){

    if( H == NULL )
    {
	printf( "H is NULL\n" );
	return -1;
    }

    linklist p = ( linklist )malloc( sizeof( listnode) );
    if( p == NULL )
    {
	printf("malloc failed\n");
	return -1;
    }

    linklist q = list_get( H, pos - 1 );
    if( q == NULL )
    {
	printf("q is NULL\n");
	return -1;
    }


    p->data = value;
    p->next = q->next;
    q->next = p;

    return 1;

}   

//显示表中所有元素
int list_show( linklist H ){

    if( H == NULL )
    {
	printf( "H is NULL\n" );
	return -1;
    }

    printf("数据: ");
    linklist p = H;
    while( ( p = p->next ) != NULL )
	printf( "%d ", p->data );

    puts("");

    return 1;
}


//删除某个节点的元素
int list_delete( linklist H, int pos ){

    if( H == NULL )
    {
	printf( "H is NULL\n" );
	return -1;
    }

    linklist p = list_get( H, pos -1 );
    if( p == NULL )
    {
	printf(" p is NULL\n");
	return -1;
    }

    if( p->next == NULL )
    {
	printf("delete pos is invalid\n");
	return -1;
    } 

    linklist q = p->next;
    p->next = p->next->next;

    free(q);
    q = NULL;

    return 1;
} 

//链表中释放所有元素
linklist list_free( linklist H ){

    if( H == NULL )
    {
	printf( "H is NULL\n" );
	return NULL;
    }

    linklist p;
    while(  H != NULL )
    {
	p = H->next;
	free(p);
	H = H->next;

    }

    return NULL;;
} 

//反转
int list_reversal( linklist H ){

    if( H == NULL )
    {
	printf( "H is NULL\n" );
	return -1;
    }

    if( H->next == NULL || H->next->next == NULL )
    {
	printf( "H not need reversal\n" );
	return 1;
    }

    linklist q ,p;
    q = p = H->next->next;
    H->next->next = NULL;

    while( q != NULL )
    {
	p = q;
	q = q->next;
	p->next = H->next;
	H->next = p;
    }



    return 1;
} 


//相邻两节点data值之和为最大的第一节点的指针,包括只含两个节点加头节点
linklist list_max( linklist H, data_t *value ){

    if( H == NULL )
    {
	printf( "H is NULL\n" );
	return NULL;
    } 

    if( H->next == NULL || H->next->next == NULL )
    {
	printf( "H is invalid\n");
	return NULL;
    }

    linklist p = H;
    linklist res = H->next;
    int max = H->next->data + H->next->next->data; //先让最大值等于第一节点和第二节点之和

    while( ( p = p->next ) != NULL )
    {
	if( p->next == NULL)
	    break;

	int val = p->data + p->next->data;
	if( val > max )
	{
	    max = val;
	    res = p;
	}

    }

    *value = max;
    return res;
}   

//将有序表A和有序表B合并表A，表A递增有序
int list_merge( linklist H1, linklist H2 ){

    if( H1 == NULL || H2 == NULL )
    {
	printf( "list is NULL\n" );
	return -1;
    } 

    if( H1->next == NULL || H2->next == NULL )
    {
	printf( "list is invalid\n");
	return -1;
    }


    linklist p = H1->next;
    linklist q = H2->next;
    H2->next = NULL;
    linklist flag = H1;
    linklist q2;

    while( p != NULL )
    {
	if( q ==NULL )
	    break;

	if( p->data >= q->data )
	{
	    q2 = q;
	    flag->next = q2;
	    q = q->next;
	    q2->next = p;

	    flag = q2;
	    continue;
	}

	flag = p;
	p = p->next;
    }

    if( q != NULL ){

	flag->next = q;
    }

    return 1;
}

//排序
int list_rank( linklist H ){

    if( H == NULL  )
    {
	printf( "list is NULL\n" );
	return -1;
    } 

    if( H->next == NULL || H->next == NULL )
    {
	printf( "list is invalid\n");
	return 1;
    }

    linklist p = H->next;
    linklist q = p;
    data_t val;

    while( p != NULL)
    {
	while( q != NULL )
	{

	    if( q->data < p->data )
	    {

		val = p->data;
		p->data = q->data;
		q->data = val;
                
		q = q->next;
		continue;
	    }

	    q = q->next;
	}

	p = p->next;
	q = p;
    }
}



